package leetcodev1.树;

import leetcodev1.链表.Solution;

import java.util.*;

public class LeetCode103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();//正序遍历时用
        Stack<TreeNode> stack = new Stack<>();//逆序遍历时用
        queue.add(root);
        int level = 0;//偶数用queue 奇数用stack
        while (!queue.isEmpty() || !stack.isEmpty()) {
            List<Integer> tmpRet = new ArrayList<>();

            if (level % 2 == 0) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode poll = queue.poll();
                    tmpRet.add(poll.val);

                    if (poll.left != null) {
                        stack.push(poll.left);
                    }

                    if (poll.right != null) {
                        stack.push(poll.right);
                    }
                }
            } else {
                int size = stack.size();
                for (int i = 0; i < size; i++) {
                    TreeNode pop = stack.pop();
                    tmpRet.add(pop.val);

                    if (pop.left != null) {
                        queue.add(pop.left);
                    }

                    if (pop.right != null) {
                        queue.add(pop.right);
                    }
                }

            }

            ret.add(tmpRet);
            level++;
        }

        return ret;
    }
}

class Answer103{
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        //双端队列
        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
}
